import java.util.Scanner;

/*
背包问题：动态规划
 */
public class Demo {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);

        int[] w={3,2,4,7};
        int[] v={5,6,3,19};
        int bag=11;

        int ret=process(w,v,bag);
        System.out.println(ret);
    }

    private static int process(int[] w, int[] v, int bag) {

        int n=w.length;
        int[][] dp=new int[n+1][bag+1];

        for(int index=n-1;index>=0;index--)
        {
            for(int rest=0;rest<=bag;rest++)
            {
                int p1=dp[index+1][rest];
                int p2=-1;
                if(rest-w[index]>=0)
                {
                    p2=v[index]+dp[index+1][rest-w[index]];
                }
                dp[index][rest]=Math.max(p1,p2);
            }
        }
        return dp[0][bag];
    }
}
